题目分析

太有趣了，某厂特别喜欢考数学题，基本上每次都有2题数学。数学是程序员的重要法宝，很多优化算法，人工智能都是建立在数学的基础上，因此学好数学才能在计算机的领域走的更好。小伙伴们不要害怕，下面看一看如何求解。

数学

我们考虑两种情况：

当L小于等于d时，不需要切割，因此输出为0
当L大于d时，则一定需要切割一次，设长度为x的木棒的切割期望为$f(x)$
- 如果切割时剩余的长度t小于等于d时，则不需要下一次切割。
- 对于切割时剩余长度t大于d小于x时，则需要以$\frac{1}{x}$的概率下一次切割，切割期望为$f(t)$

因此可以得到下面这个方程
$$f(x) = 1 + \frac{1}{x} \int_d^x f(t)dt \ \ \textcircled{1}$$
将等式两边同时求导
$$f’(x) = -\frac{1}{x^2} \int_d^x f(t)dt + \frac{f(x)}{x} \ \ \textcircled{2}$$
将$\textcircled{1}$式进行变换
$$-\frac{1}{x^2} \int_d^x f(t)dt = -\frac{1}{x}(f(x) - 1)$$
然后代入$\textcircled{2}$式，可得
$$f’(x) = \frac{1}{x}$$
则有
$$f(x) = ln(x) + C$$
将边界点$f(d) = 1$代入，可得
$$1 = ln(d) + C$$
因此$C = 1 - ln(d)$，所以期望可以写为
$$f(x) = \begin{cases} 0 & x \le d \ ln(\frac{x}{d}) + 1 & x > d \end{cases}$$
得到公式以后，求解就迎刃而解了。算法的**时间复杂度为$O(1)$，空间复杂度为$O(1)$**。

import sys
import math


for line in sys.stdin:
    L, d = [int(x) for x in line.strip().split()]
    print('0.0000') if L <= d else print('%.4f' % (math.log(L / d) + 1))

刷题总结

这类题目往往有两个思路，一个是代入公式进行推导计算，例如本题，求出最后的表达式，因为不涉及算法层面，只是考察数学运用能力，所以这种题型较少。更多题型的是使用递归的思路进行迭代计算，当满足一定条件，通常是误差小于指定精度停止计算，得到最后的结果。这两种题型不难，但是如果没有见过可能很难想到，因此小伙伴们需要掌握几道这种类型的题目。